package leetcode.day_2020_12_07_12_14;

import java.util.Arrays;

/**
 * 198. 打家劫舍
 */
public class L_198 {
    static int[] mem;
    public static void main(String[] args) {
        int[] nums = {114,117,207,117,235,82,90,67,143,146,53,108,200,91,80,223,58,170,110,236,81,90,222,160,165,195,187,199,114,235,197,187,69,129,64,214,228,78,188,67,205,94,205,169,241,202,144,240};
        System.out.println(rob(nums));
    }

    public static int rob(int[] nums) {
        // return dp(nums, 0);

//        mem = new int[nums.length];
//        Arrays.fill(mem, -1);
//        return dp2(nums, 0);

        return rob3(nums);
    }

    /**
     * 超出时间限制
     * @param nums
     * @param start
     * @return
     */
    public static int dp(int[] nums, int start) {
        if (nums.length <= start) {
            return 0;
        }
        int res = Math.max(dp(nums, start+1), nums[start] + dp(nums, start+2));
        return res;
    }

    /**
     * 备忘录法
     * 自顶向下
     * @param nums
     * @param start
     * @return
     */
    public static int dp2(int[] nums, int start) {
        if(nums.length <= start) {
            return 0;
        }
        if (mem[start] != -1) return mem[start];
        int res = Math.max(dp2(nums, start+1), nums[start] + dp2(nums, start+2));
        mem[start] = res;
        return res;
    }

    /**
     * 自底向上
     * @param nums
     * @return
     */
    public static int rob2(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+2];
        for(int i=n-1; i>=0; i--) {
            dp[i] = Math.max(dp[i+1], nums[i]+dp[i+2]);
        }
        return dp[0];
    }

    /**
     * 最近两个状态
     */
    public static int rob3(int[] nums) {
        int n = nums.length;
        // 记录dp[i+1], dp[i+2]
        int dp_i_1 = 0, dp_i_2 = 0;
        // 记录dp[i]
        int dp_i = 0;
        for(int i=n-1; i>=0; i--) {
            dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }
}
